package _18_剑指OfferII;

public class _096_剑指OfferII字符串交织 {

    public static void main(String[] args) {

        _096_剑指OfferII字符串交织 v = new _096_剑指OfferII字符串交织();

        String str1 = "ab";
        String str2 = "bc";
        String str3 = "bbac";
        System.out.println(v.isInterleave(str1, str2, str3));

    }

    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 + len2 != s3.length()) return false;
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        // 初始化dp数据
        dp[0][0] = true;
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }
        for (int i = 1; i <= len2; i++) {
            dp[0][i] = dp[0][i - 1] && s2.charAt(i - 1) == s3.charAt(i - 1);
        }

        // 遍历
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                int end = i + j - 1;
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(end)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(end));
            }
        }
        return dp[len1][len2];
    }
}
